package org.algorithm.biubiu.wheel_1.DFS算法;

/**
 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/surrounded-regions/   130
 */
public class $5月2日$被围绕的区域 {


    class Solution {
        int row;
        int col;
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            row =board.length;
            col =  board[0].length;

            for(int i=0;i<row;i++){
                dfs(board,i,0);
                dfs(board,i,col-1);
            }
            for(int i=0;i<col;i++){
                dfs(board,0,i);
                dfs(board,row-1,i);
            }

            for (int y = 0; y < row; y++) {
                for (int x = 0; x < col; x++) {
                    if (board[y][x] == 'O') {
                        board[y][x] = 'X';
                    }
                    if (board[y][x] == '-') {
                        board[y][x] = 'O';
                    }
                }
            }

        }

        public void dfs(char[][] board,int y,int x){
            if(x<0 || y<0 || x>=col || y >=row || board[y][x]!='O'){
                return;
            }
            board[y][x] = '-';
            dfs(board, y - 1, x); // 上
            dfs(board, y + 1, x); // 下
            dfs(board, y, x - 1); // 左
            dfs(board, y, x + 1); // 右
            return ;
        }
    }

}
